import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {
    public boolean isSubsequence (String S, String T) {
        int i = 0, j = 0;
        if(S.length() > T.length()){
            return false;
        }
        for(i = 0; i < S.length(); i++){
            int flag = 0;
            for(; j < T.length(); j++){
                if(S.charAt(i) == T.charAt(j)){
                    flag = 1;
                    j++;
                    break;
                }
            }
            if(flag == 0){
                return false;
            }
        }
        return true;
    }

    class MyComparator implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    }

    public int[] smallestK(int[] arr, int k) {
        if(k == 0){
            return new int[0];
        }
        int i = 0;
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, new MyComparator());
        for(i = 0; i < k; i++){
            priorityQueue.offer(arr[i]);
        }
        for(; i < arr.length; i++){
            if(priorityQueue.isEmpty()){
                priorityQueue.offer(arr[i]);
            }else{
                int top = priorityQueue.peek();
                if(arr[i] <= top){
                    priorityQueue.offer(arr[i]);
                }
            }
        }
        int[] ans = new int[k];
        i = 0;
        while(!priorityQueue.isEmpty()){
            ans[i++] = priorityQueue.poll();
        }
        return ans;
    }
}
